package com.lmk.dsa.struct.graph;

import java.util.ArrayList;
import java.util.List;
import com.lmk.dsa.struct.commons.Edge;

/**
 * 稀疏图，使用邻接表实现
 * @author LaoMake
 * @since 1.0
 */
public class SparseGraph extends Graph {

	/** 邻接表 */
	private ArrayList<Edge>[] table;

	public SparseGraph(int n) {
		super(n);
		table = new ArrayList[n];
		for(int i = 0; i < n; i++) {
			table[i] = new ArrayList<Edge>();
		}
	}
	
	public SparseGraph(Object[] array) {
		super(array);
		table = new ArrayList[n];
		for(int i = 0; i < n; i++) {
			table[i] = new ArrayList<Edge>();
		}
	}

	@Override
	public List<Edge> adjoinEdge(int index) {
		return table[index];
	}

	@Override
	public List<Integer> adjoinVertex(int index) {
		List<Edge> list = table[index];
		List<Integer> vertexes = new ArrayList<>(list.size());
		for (Edge edge : list){
			vertexes.add(edge.to);
		}
		return vertexes;
	}

	/**
	 * 获取邻接表
	 * @return
	 */
	public ArrayList<Edge>[] getTable() {
		return this.table;
	}

	@Override
	public void addEdge(int from, int to, int weight) {
		assert from >= 0 && from < n : "from 越界";
		assert to >= 0 && to < n : "to 越界";
		assert from != to : "起始索引不能与目标索引相同";
		assert weight > 0 : "权值必须大于0";
		
		if(!hasEdge(from, to)) { // 消除平行边，会有额外的消耗
			List<Edge> list = table[from];
			list.add(new Edge(from, to, weight));

			if(!directed){
				list = table[to];
				list.add(new Edge(to, from, weight));
			}

			m++;
		}
	}

	@Override
	public Integer weight(int from, int to) {
		Integer weight = null;
		
		List<Edge> list = table[from];
		for(Edge e : list) {
			if(e.to == to) {
				weight = e.weight;
				break;
			}
		}
		return weight;
	}

	@Override
	public boolean hasEdge(int from, int to) {
		assert from >= 0 && from < n : "from 越界";
		assert to >= 0 && to < n : "to 越界";
		assert from != to : "起始索引不能与目标索引相同";

		// 检查邻接表
		boolean hasEdge = false;
		List<Edge> list = table[from];
		for(Edge e : list) {
			if(e.to == to) {
				hasEdge = true;
				break;
			}
		}

		return hasEdge;
	}
	
	@Override
	public void show() {
		for (int i = 0; i < n; i++) {
			System.out.print(i + ": ");
			System.out.print(table[i]);
			System.out.println();
		}
	}
}


